package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 需要复习
 * @author Wenhao Tong
 * @create 2021-07-17 20:32
 */
public class LeetCode139 {
    public static void main(String[] args) {
        LeetCode139 leetCode139 = new LeetCode139();
        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
        boolean leetcode = leetCode139.wordBreak("leetcode", list);
        System.out.println(leetcode);
    }
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> wordDictSet = new HashSet(wordDict);
            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 0; j < i; j++) {
                    if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
}
